package _14_滑动窗口;

import java.util.*;

public class _187_重复的DNA序列 {


    public static void main(String[] args) {

        _187_重复的DNA序列 v = new _187_重复的DNA序列();
        String str = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
        List<String> list = v.findRepeatedDnaSequences(str);
        for (String s : list) {
            System.out.println(s);
        }
    }

    // 使用两个HashSet判断
    public List<String> findRepeatedDnaSequences(String s) {
        int strLen = 10;
        HashSet<String> input = new HashSet<>();
        HashSet<String> output = new HashSet<>();
        int end = s.length() - strLen;
        for (int i = 0; i <= end; i++) {
            String cur = s.substring(i, i + strLen);
            if (!input.add(cur)) output.add(cur);
        }
        return new ArrayList<>(output);
    }


    public List<String> findRepeatedDnaSequences2(String s) {
        List<String> results = new ArrayList<>();
        int strLen = 10;
        if (s.length() <= strLen) return results;
        char[] chars = s.toCharArray();
        Map<String, Integer> map = new HashMap<>();
        int end = chars.length - strLen;
        for (int i = 0; i <= end; i++) {
            String cur = new String(chars, i, strLen);
            Integer flag = map.put(cur, map.getOrDefault(cur, 0) + 1);
            if (flag != null && flag == 1) {
                results.add(cur);
            }
        }
        return results;
    }

    public List<String> findRepeatedDnaSequences1(String s) {
        List<String> results = new ArrayList<>();
        int strLen = 10;
        if (s.length() <= strLen) return results;
        char[] chars = s.toCharArray();
        int end = chars.length;
        Map<String, Integer> map = new HashMap<>();
        // 存入初始数据
        map.put(new String(chars, 0, strLen), 1);
        for (int i = strLen + 1; i <= end; i++) {
            String cur = new String(chars, i - strLen, strLen);
            map.put(cur, map.getOrDefault(cur, 0) + 1);
        }
        // 筛选出数据
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() > 1) {
                results.add(entry.getKey());
            }
        }
        return results;
    }

}
